Image('images/medieval_hydraulic_engineering.jpg')
French King Henri IV hired the Italian engineer Tomaso Francini to build him some waterworks for the royal palace at Saint Germain en Laye. Francini built hydraulic grottoes devoted to the Greek pantheon and their adventures: Mercury played a trumpet and Orpheus his lyre; Perseus freed Andromeda from her dragon. There were automaton blacksmiths, weavers, millers, carpenters, knife-grinders, fishermen, and farriers conducting the obligatory watery attacks on spectators.
Cite: Riskin, J. (n.d.). Frolicsome Engines: The Long Prehistory of Artificial Intelligence. Retrieved April 10, 2018, from https://publicdomainreview.org/2016/05/04/frolicsome-engines-the-long-prehistory-of-artificial-intelligence/
Image('images/Figure-S5-2-minmax-tree-example.png')
Alpha-Beta is layered on top of minimax
Remember that minimax search is depth-first
Only consider nodes along a single path
Alpha–beta pruning uses two parameters describing the bounds on backed-up values found along the path:
α = highest-value found so far for MAX along path.
β = lowest-value found so far for MIN along path.
Once a better play has been found, prune all other branches as high in the tree as possible.
Image('images/Figure-S5-5-alphpabeta-pruning-example.png')
Atomic representations is what we have used in our study of search
Factored representation
Splits up each state into a fixed set of variables or attributes, each of which can have a value
Commonly used in machine learning tasks
Image('images/Figure-S2-16-state-representations.png')
Image('images/usa-states-map.png')
Image('images/Figure-S6-1-graph-coloring.png')
Can you color Australia with just 3 colors?
Google aima-javascript
Click on View the Visualizations > Go to Part 2 > Chapter 6 Constraint Satisfation Problems
Or, just go to AIMA Visualizations - Constrain Satisfaction
Image('images/map-coloring-solution.png')
Domain - Time range
Variable - Start time, end time
Constraint - Start_Time_2 > Start_Time_1 + Duration_1
Image('./images/time-travelers-convention_order_for_slides.png')
Idea: Look ahead and prune domains of unassigned variables
After assignment eliminate incompatible values from neighbors domains
Re-instate values when backtracking
Image('./images/time-traverlers-dfs-solution.jpg')
Image('./images/time-travelers-convention_order_for_slides.png')
Perform DFS + FC
If a new singleton domains are created propagate through the singleton's neighbors
Propigate == Remove inconsistent values from neighbors
Repeat if any new singletons result, propagate through them too
Image('./images/time-travelers-convention_order_for_slides.png')
Image('images/arc-consistency-graph.png')
Image('images/arc-consistency-tree.png')
Idea: Eliminate conflicting domain values before search
function AC-3(csp) returns false if an inconsistency is found and true otherwise
inputs: csp, a binary CSP with components (X, D, C)
local variables: queue, a queue of arcs, initially all the arcs in csp
while queue is not empty do
(Xi, Xj) ← REMOVE-FIRST(queue)
if REVISE(csp, Xi, Xj) then
if size of Di = 0 then return false
for each Xk in Xi.NEIGHBORS − {Xj} do
add(Xk, Xi) to queue
return true
function REVISE(csp, Xi, Xj) returns true iff we revise the domain of Xi
revised ← false
for each x in Di do
if no value y in Dj allows (x, y) to satisfy the constraint between Xi and Xj then
delete x from Di
revised ← true
return revised
Image('images/arc-consistency-graph.png')
Image('https://imgs.xkcd.com/comics/python_environment.png')